The nonblocking of cross connect switches in a communications network assesses the ability to route connections from input ports to output ports. A cross connect C can be thought of as a directed graph where input ports are nodes with no incoming edges and output ports are nodes with no outgoing edges. A request for a connection from an input port a to an output port b will be a request for a directed path from a to b. For a more detailed discussion of nonblocking cross connects, see, for example, J. Y. Hui., Switching and Traffic Theory for Integrated Broadband Networks, Kluwer Academic Publishers, Norwell, Mass. (1990) and G. M. Masson et al., “A Sampler of Circuit Switching Networks,” IEEE Computer, 5:32-48 (June 1979).
For many networks, however, such as long-haul optical networks, connection requests have “bidirectional symmetry.” In other words, there is a request to connect i to j if and only if there is also a request to connect j to i and moreover these two connections should be routed on the same bidirectional links. See, J. Simmons et al., “Optical Crossconnects of Reduced Complexity for WDM Networks with Bidirectional Symmetry, IEEE Photonics Technology Letters, 10(6):819-821 (June 1998). This is due to the fact that optical network management is typically designed to connect transceivers in pairs. A restriction to bidirectional demands may allow for simplified cross connect designs. For bidirectional demands, a cross connect will not have input and output ports, instead it will just have ports.
The cross connect will be an undirected network where the ports are leaf nodes and a request for a connection will be a request for an undirected path between two ports. This is of interest when one has symmetric demands (i.e., there is a demand d from node i to node j if and only if there is a demand d′ from node j to node i) and moreover demands d and d′ should be routed along the same undirected path.
A cross connect is said to be strictly nonblocking if all connections from input ports to output ports can be routed without disturbing other connections. A cross connect is said to be widesense nonblocking if there exists a routing algorithm such that if all previous connections have been routed using that algorithm, then that algorithm will find a route for any subsequent connection requests.
A need exists for a modification to traditional cross connect designs for this undirected case. A further need exists for improved cross connect designs for the undirected case that exhibit good nonblocking properties. Yet another need exists for improved cross connect designs based on various four-port switches.